package top.datacluster.basic.algorithm.leetcode.tree;

import top.datacluster.basic.algorithm.leetcode.TreeNode;

import java.util.Stack;

public class LeetCode1614 {



    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        Stack<TreeNode> pParent = new Stack<>();
        Stack<TreeNode> qParent = new Stack<>();

        getParent(root, p, pParent);
        getParent(root, q, qParent);

        TreeNode reslut = root;
        while (!pParent.isEmpty() && !qParent.isEmpty()){
            if (pParent.peek().val == qParent.peek().val){
                reslut = pParent.pop();
                qParent.pop();
            }else{
                break;
            }
        }
        return reslut;
    }

    public boolean getParent(TreeNode root, TreeNode val, Stack<TreeNode> stack){
        if (root == null){
            return false;
        }
        if (root.val != val.val){
            if (getParent(root.left, val, stack)){
                stack.push(root);
                return true;
            }else if (getParent(root.right, val, stack)){
                stack.push((root));
                return true;
            }else{
                return false;
            }
        }else{
            stack.push(root);
            return true;
        }
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(6);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(0);
        TreeNode node7 = new TreeNode(8);
        TreeNode node8 = new TreeNode(7);
        TreeNode node9 = new TreeNode(4);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node5.left = node8;
        node5.right = node9;
        System.out.println(new LeetCode1614().lowestCommonAncestor(node1, node2, node9).val);
    }
}
